package org.example.leetcode;
import org.example.sword2offer.primary.Q68_1_TreeNodeCommonParentNode;

import java.util.*;
/**
 * @version 1.0.0
 * @author: lynn
 * @description:给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 K ;
 * 返回到目标结点 target 距离为 K 的所有结点的值的列表。 答案可以以任何顺序返回
 * @date: 2021/7/28 9:02
 */
public class LC863 {
    public static void main(String[] args) {
        TreeNode treeNode=new TreeNode(8);
        treeNode.left=new TreeNode(4);
        treeNode.right=new TreeNode(10);
        treeNode.left.left=new TreeNode(11);
        treeNode.left.right=new TreeNode(6);
        treeNode.right.left=new TreeNode(5);
        treeNode.right.right=new TreeNode(12);
        treeNode.right.right.right=new TreeNode(16);
        LC863 lc=new LC863();
        System.out.println(lc.distanceK(treeNode,10,2));
    }
    public List<Integer> distanceK(TreeNode root, int target, int k) {
        List<Integer> list=new ArrayList<>();
        if (root==null) return list;
        Stack<Integer> stack=new Stack<>();
        List<List<Integer>> treeList=new ArrayList<>();;
        findTrees(root,stack,target,treeList);
        getDistanceKList(treeList,target,k,list);
        return list;
    }
    private void getDistanceKList(List<List<Integer>> treeList,int target,int k,List<Integer> list){
        for (int i = 0; i <treeList.size() ; i++) {
            for (int j = 0; j <treeList.get(i).size() ; j++) {
                if (treeList.get(i).get(j)==target ){
                    if (j-k>=0)  list.add(treeList.get(i).get(j-k));
                    if (j+k<treeList.get(i).size()) list.add(treeList.get(i).get(j+k));
                }
            }
        }
    }

    private void findTrees(TreeNode root,Stack<Integer> stack,int target,List<List<Integer>> treeList){
        if (root==null) return;
        stack.push(root.val);
        if (root.left==null && root.right==null && stack.contains(target)){
            List<Integer> tmpList=new ArrayList<>();
            tmpList.addAll(stack);
            treeList.add(tmpList);
        }
        findTrees(root.left,stack,target,treeList);
        findTrees(root.right,stack,target,treeList);
        stack.pop();
    }

    private static class TreeNode{
        TreeNode left;
        TreeNode right;
        int val;
        TreeNode(int val){
            this.val=val;
        }
    }
}
